1. Field of the Invention
The present invention relates to methods and apparatus for classifying packets that can follow an adaptive path over a communications network employing global addressing.
2. Description of Related Art
A global communications network such as the Internet can carry information for a variety of applications such as voice, video, and VPNs. Internet service providers (ISPs) need to distinguish between these different packet flows, so that each packet flow can receive its appropriate quality-of-service (QoS). These packets ought to be classified according to the bit patterns within the packet.
It is highly desirable to use protocols in such a way as to provide an appropriate QoS to current and future applications using the networks. Unfortunately, the classification problem is algorithmically difficult; that is, classification will take a relatively long time, will require expensive special-purpose hardware, or both.
In most cases, the solution to the classification problem is assumed to occur at an Internet “edge router” (i.e., at the edge of the ISP's network). However, considering the ever-increasing bandwidth requirements of Internet routers, classification seem likely to remain a speed bottleneck for many routers. Furthermore, providing classification hardware at each input line is expensive: just designing and implementing a packet classifier in hardware is expected to take well over a year even with the support of dozens of hardware and software engineers.
A conventional classification technique is to require Internet routers to examine the headers of higher-level protocols to determine the type of application. This technique, however, requires excessive coordination to maintain an appropriate QoS with ISPs, especially as users begin using new applications and new higher-level protocols. It also violates the network layering principle, which places certain functions at designated levels. Under the layering diagram of FIG. 1 the IP protocol operates at the network layer 14 (layer 3), while the TCP protocol operates at the transport layer 16 (layer 4). Higher layers are shown collapsed into session/presentation/application layer 18.
In the future, many users will require that the secrecy of their Internet traffic be maintained. This will be handled with encryption as described by the IPsec standard. Unfortunately, when encryption is used, the higher-level protocol headers are not available to intermediate routers, and correct classification is impossible with the traditional approaches. Thus, security is incompatible with QoS if packet classification occurs at the Internet backbone.
In the initial design of the Internet, there was no provision for QoS. Routers would examine the IP header of an incoming packet, extract the destination IP address, and forward the packet to the “next hop” after consulting a lookup table indexed by IP addresses. This approach of determining forwarding by consulting a fixed field within the packet has several advantages, including speed, simplicity, and modularity. However, if QoS is to be supported, routers cannot treat all packets the same just because they have the same destination IP address.
To maintain generality, references herein to IP protocols or Internet communications will be deemed to include communication techniques and protocols that exist now or may exist in the future to allow forwarding of packets to a destination by using a global addressing scheme (whether or not the network in fact has a reach that is global or very restricted) along an adaptive path, that is, a path that may change to accommodate traffic load or to circumvent networks or nodes having difficulties.
FIGS. 2 and 3 show the format of an TCP/IP packet. All IP packets contain an IP header, which will contain, among other things, a source IP address (32 bit source identification code), a destination IP address (32 bit destination code), and a protocol field (8 bits). The IP header includes a Type of Service field (TOS field, enlisted herein to carry a service code). In practice, most hosts and routers do not use the TOS field. However, this field was defined in RFC 791 [infra., Bibliography 3] to give “hints” to routers as to the kind of service the packet should receive. In that document, the 8-bit TOS field is broken up into a 3-bit precedence field (000 being normal precedence at one extreme and 111 being network control precedence at the other), 1 bit to request low delay service, 1 bit to request high throughput service, 1 bit to request high reliability service, and 2 unused bits.
As shown in FIG. 2, each IP packet has a number of fields outside the IP header that can be used for classification. Field matching may be based on specific (distinct) values, ranges of values, or prefixes. It is possible to examine any portion of an IP packet for the purposes of classification. In practice, it is probably only the first few headers that will be considered for this purpose.
Traditionally, all these fields will typically be used for packet classification, in combination with the data portion of an IP packet. This data portion may contain a TCP segment, as shown in FIG. 4. In this case, it is likely the classifying mechanism will consider the TCP source port (16 bits) and the TCP destination port (16 bits). Higher-layer (or application-layer) headers can also be used for classification purposes. In general, it does not matter which protocols are using IP. If the classifier understands the protocols in use, classification based on header fields is possible.
Unfortunately, the classification technique just described makes prohibitive demands on resources in the general case. Assuming a set of n objects (corresponding to packet flow classes) in d dimensions (corresponding to fields in the packet used for classification), the best known algorithms run in either O(logd−1 n) time with O(n) space, or O(log n) time with O(nd) space. In other words, either exponential time or space (relative to the dimension of the classification) will be needed. See M. H. Overmars and A. F. van der Stappen, “Range Searching and Point Location among Fat Objects,” Journal of Algorithms, vol. 21, no. 3, pp. 629-656, 1996.
To take a more practical view, n may grow large in real systems, but the size of d is likely to be quite limited. For example, the literature describes packet-filtering gateways—a similar application—as using source and destination IP addresses, the protocol field in the IP header, the source and destination TCP (or UDP) ports, and TCP (or UDP) flags. See W. R. Cheswick and S. M. Bellovin, Firewalls and Internet Security: Repelling the Wily Hacker, Addison-Wesley, Reading, Mass., 1994.
Typically, classification is assumed to occur at the “edge router” (i.e., at the edge of the ISP's network or other domain boundary). A conventional approach to packet classification assumes that routers between an enterprise network and a core backbone network are performing the classification. For example, the packet classification approaches described by Srinivasan et al. [Bibliography 9, 10], Lakshman and Stiliadis [Bibliography 8], and Gupta and McKeown [Bibliography 11] all assume such an environment. However, even for moderate sizes of d, packet classification at wire speeds of OC-48 (2.4 Gbps) or OC-192 (10 Gbps) is likely to be a difficult and expensive proposition. If implemented in software, packet classification will almost certainly be a bottleneck limiting line throughput. If implemented in hardware, classification will be very expensive and inflexible, and it can easily remain a bottleneck.
To deal with QoS issues the Diffserv standard was introduced, as described in RFC 2474. With Diffserv the TOS field (Type of Service field of FIG. 3) is redefined to specify use in a way distinct from the earlier IPv4 and IPv6 standards. See, K. Nichols, S. Blake, F. Baker, and D. Black, “Definition of the Differentiated Services Field (DS Field) in the IPv4 and IPv6 Headers,” RFC 2474, December 1998. With Diffserv, the TOS field is renamed the Differentiated Services Field (DS Field). Six bits are used to indicate the Differentiated Services Codepoint (DSCP), and two bits are unused. The Diffserv standard contemplates use with a range of queue service and/or queue management disciplines inside a “DS domain boundary.” It is still up to routers at the edge of this DS domain boundary to ensure that all traffic entering the domain is marked with codepoint values appropriate to the traffic and the domain, remarking the traffic with new codepoint values if necessary. Therefore, the Diffserv standard does not solve the problems of transferring data across overloaded edge routers. Moreover, the Diffserv standard assumes replacement of the IPv4 and IPv6 standards for networks that will support QoS. This may require a large capital investment to replace routers operating inside a DS domain boundary.
In U.S. Pat. No. 6,046,979 layer 3 and 4 header information from the TCP/IP protocols are stored in a linked memory index using an ASIC. The user can specify a bandwidth based upon the application (HTTP, FTP, etc.) and based upon the source and the destination of packets. The system uses a credit bucket approach to regulate the bandwidth for a particular flow. This approach requires culling out high-level application information and will be relatively complex and slow, as noted above.
In U.S. Pat. No. 6,046,980 traffic flows can be classified based on the type of service (FTP, Web, etc.), the type of data object (*.gif, *.avi, etc.), the class of users (a department in an enterprise), or a TCP data rate detected by an autobaud component. Based on the classification, a specific flow can be given a preferred or guaranteed bandwidth. Again, this reference works on a relatively high level and will be relatively complex and slow.
For other references working above level 3, see U.S. Pat. No. 6,018,530 (TCP header is modified to (a) use a generally unused, reserved section, and (b) insert specialized information into certain option fields); and U.S. Pat. No. 5,506,834 (LAN interface examines identifying information existing at the application level, such as the FTP control frame);
ATM is a standard protocol for transmitting asynchronous telecommunications data. This protocol is based on the transmission of data in fixed size data packets known as ATM cells. The ATM protocol is connection oriented. Specifically, an ATM network will establish at the outset a path through the network that persists so long as the connection lasts. While the ATM protocol offers quality of service features that let customers prioritize certain types of traffic, granting a level of service can be difficult when packets from different sources arrive sporadically, as is the case with ordinary Internet traffic. Much work has been done to allow transmission of IP packets over an ATM network, but these approaches have not satisfactorily solved the task of efficiently handling quality of service requests at the edge router.
For various approaches to handling quality of service issues for an ATM network, see U.S. Pat. No. 6,041,039 (Generic Flow Control field in the ATM header may be set by the sender to designate the cell priority level and whether the service is to be real-time); U.S. Pat. No. 6,041,054 (enhance bandwidth for IP packets using ATM adaption layer 2 (AAL2) by sending an address to a lookup table in place of repetitive portions of the header); U.S. Pat. No. 6,049,544 (a voice server module in an ATM switch examines flag bits indicating data compression, facsimile tone detection, silence, etc.); and U.S. Pat. No. 6,178,169 (ATM cells are given a header with source and destination information before being sent in a connectionless manner).
See also U.S. Pat. No. 6,044,081 (signaling information is sent separately over a non-isochronous packet network to support isochronous communications); U.S. Pat. No. 5,999,518 (data packet routed based on list of addresses at packet switch, otherwise handed off to next switch); and U.S. Pat. No. 5,694,548.
Bibliographic References
[1] M. H. Overmars and A. F. van der Stappen, “Range Searching and Point Location among Fat Objects,” Journal of Algorithms, vol. 21, no. 3, pp. 629-656, 1996.
[2] W. R. Cheswick and S. M. Bellovin, Firewalls and Internet Security: Repelling the Wily Hacker, Addison-Wesley, Reading, Mass., 1994.
[3] J. Postel, Editor, “Internet Protocol,” STD 5, RFC 791, September 1981.
[4] K. Nichols, S. Blake, F. Baker, and D. Black, “Definition of the Differentiated Services Field (DS Field) in the IPv4 and IPv6 Headers,” RFC 2474, December 1998.
[5] E. C. Rosen, Y. Rekhter, D. Tappan, D. Farinacci, G. Fedorkow, T. Li, and A. Conta, “MPLS Label Stack Encoding,” Work in Progress, September 1999.
[6] F. Baker, Editor, “Requirements for IP Version 4 Routers,” RFC 1812, June 1995.
[7] D. E. Knuth, The Art of Computer Programming, Volume 3, Sorting and Searching,” second edition, Addison-Wesley, Reading, Mass., 1998.
[8] T. V. Lakshman and D. Stiliadis, “High-speed Policy-based Packet Forwarding Using Efficient Multi-dimensional Range Matching,” in SIGCOMM'98, Vancouver, BC, October 1998.
[9] V. Srinivasan, G. Varghese, S. Suri, and M. Waldvogel, “Fast and Scalable Layer Four Switching,” in SIGCOMM'98, Vancouver, BC, October 1998.
[10] M. Degermark, A. Brodnik, S. Carlsson, and S. Pink, “Small Forwarding Tables for Fast Routing Lookups,” in SIGCOMM'97, Cannes, France, 1997.
[11] M. Waldvogel, G. Varghese, J. Turner, and B. Plattner, “Scalable High Speed IP Routing Lookups,” in SIGCOMM'97, Cannes, France, 1997.
[12] P. Gupta, S. Lin, and N. McKeown, “Routing Lookups in Hardware at Memory Access Speeds,” in INFOCOM'98, San Francisco, Calif., April 1998.
[13] B. Lampson, V. Srinivasan, and G. Varghese, “IP Lookups Using Multiway and Multicolumn Search,” in INFOCOM'98, San Francisco, Calif., April 1998.
[14] T.-C. Church and P. Pradhan, “High Performance IP Routing Table Lookup Using CPU Caching,” in INFOCOM'99, New York, N.Y., 1999.
[15] N.-F. Huang, S.-M. Zhao, J.-Y. Pan, and C.-A. Su, “A Fast IP Routing Lookup Scheme for Gigabit Switching Routers,” in INFOCOM'99, New York, N.Y., 1999.
[16] G. Cheung and S. McCanne, “Optimal Routing Table Design for IP Address Lookups under Memory Constraints,” in INFOCOM'99, New York, N.Y., 1999.